package com.daji.base_data_structure.Tree.binary_tree;

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTreeAPI {
    //Definition for a binary tree node.
//    public  class TreeNode {
//        int val;
//        TreeNode left;
//        TreeNode right;
//
//        //Constructor
//        TreeNode() {
//        }
//
//        TreeNode(int val) {
//            this.val = val;
//        }
//
//        TreeNode(int val, TreeNode left, TreeNode right) {
//            this.val = val;
//            this.left = left;
//            this.right = right;
//        }
//    }

    /**
     * 进去是数组，吐出来是一个二叉树（层序插入）
     * 比如入参是： [3,9,20,null,null,15,7]
     * 那么返回值就是如下图的二叉树结构：
     *       3
           / \
          9  20
            /  \
           15   7
     * 思想是通过队列来对二叉树的结点进行操作。
     * 入队根结点，先后插入左右，
     * @param arr
     * @return
     */
    public TreeNode initBinaryTree(Integer[] arr) {
        if (arr.length == 0) {   //边界检查
            return null;
        }
        //新建一个TreeNode作为根节点
        TreeNode treeNode = new TreeNode(arr[0], null, null);
        //使用LinkedList模拟Queue，add为enqueue，remove为dequeue,peak为获取队列头元素
        Queue<TreeNode> queue = new LinkedList<>();
        int i = 1;
        queue.add(treeNode);
        while (i < arr.length) {
            TreeNode peek = queue.peek();   //当前队列头元素
            if (arr[i] != null) {
                peek.left = new TreeNode(arr[i], null, null);
                queue.add(peek.left);   //enqueue
            } else {
                peek.left = null;   //如果为空，直接插入空，且不enqueue
            }
            i++;
            if (i >= arr.length) {
                break;
            }
            if (arr[i] != null) {
                peek.right = new TreeNode(arr[i], null, null);
                queue.add(peek.right);  //enqueue
            } else {
                peek.right = null;   //如果为空，直接插入空，且不enqueue
            }
            i++;
            queue.remove(); //dequeue
        }
        return treeNode;
    }

    /**
     * 有序数组构建成二叉搜索树，数组必须是有序的！！！
     * Leetcode：108. 将有序数组转换为二叉搜索树
     * 思想：不停地递归取得数组的中点，插入到左/右子树当中。
     * 注意：最终得到的树，是【平衡二叉搜索树（Balanced Binary Search Tree）】，同时也是AVL树，同时也是红黑树
     * 红黑树，AVL树，平衡二叉搜索树见下面文章：
     * https://blog.csdn.net/sj15814963053/article/details/123562477
     * 
     * @param arr 排好序的有序数组
     * @param start 
     * @param end
     * @return 
     */
    public TreeNode initBinarySearchTree(Integer[] arr, int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = (start + end) / 2;

        TreeNode treeNode = new TreeNode(arr[mid], null, null);     //在中点创建一个结点作为根节点
        treeNode.left = initBinarySearchTree(arr, start, mid - 1);
        treeNode.right = initBinarySearchTree(arr, mid + 1, end);

        return treeNode;
    }

    //按照层序的顺序打印该二叉树
    public void levelOrderPrint(TreeNode root) {
        StringBuilder stringBuilder = new StringBuilder();
        if (root == null) {
            System.out.println("树为空！");
        } else {
            stringBuilder.append(root.val + " ");
            //System.out.println(root.val);
        }
        //使用LinkedList模拟Queue，add为enqueue，remove为dequeue,peak为获取队列头元素
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (queue.size() != 0) {
            TreeNode peek = queue.peek();   //当前队列头元素
            /*if (peek != null){
                System.out.println(peek.val);
            }else {
                System.out.println("null");
            }*/
            if (peek.left != null) {
                //System.out.println(peek.left.val);
                stringBuilder.append(peek.left.val + " ");
                queue.add(peek.left);
            } else {
                stringBuilder.append("null ");
            }

            if (peek.right != null) {
                //System.out.println(peek.right.val);
                stringBuilder.append(peek.right.val + " ");
                queue.add(peek.right);
            } else {
                stringBuilder.append("null ");
            }
            queue.remove(); //dequeue
        }
        System.out.println(stringBuilder);
    }

    /**
     * 层序遍历二叉树（队列思想）
     * @param root 二叉树头节点
     * @return 按照层序顺序排列好的数组
     */
    public Integer[] levelOrderTraverse(TreeNode root) {
        //频繁插入元素的场景，LinkedList性能比ArrayList更高
        LinkedList<Integer> resultList = new LinkedList<>();
        //构建队列
        Queue<TreeNode> queue = new LinkedList<>();
        //边界条件：树为空，就返回空数组
        if(root == null){
            return resultList.toArray(new Integer[resultList.size()]);
        }
        //头结点入队
        queue.add(root);
        resultList.add(root.val);
        while(true){
            TreeNode head = null;
            //请出去队列的头结点（由于队列先进先出，请出来的是最先进去的那位）
            if(queue.size() != 0){  
                head = queue.remove();
            }else{
                break;  //队列为空，无法remove，直接退出循环
            }
            
            if(head == null) {  //队列为空，直接打破循环，说明构建完毕！
                break;
            }
            if(head.left != null){
                queue.add(head.left);
                resultList.add(head.left.val);
            }
            if(head.right != null){
                queue.add(head.right);
                resultList.add(head.right.val);
            }
        }

        return resultList.toArray(new Integer[resultList.size()]);
    }

    /**
     * 前序遍历二叉树（根左右）
     * @param root 二叉树头节点
     * @return 按照前序顺序排列好的数组
     */
    public Integer[] preOrderTraverse(TreeNode root) {
        
        //频繁插入元素的场景，LinkedList性能比ArrayList更高
        LinkedList<Integer> list = new LinkedList<>();
        //将LinkedList转换成普通的数组
        LinkedList<Integer> resultList = preOrderAppend(root, list);
        return resultList.toArray(new Integer[resultList.size()]);
    }

    private LinkedList<Integer> preOrderAppend(TreeNode root, LinkedList<Integer> list){

        if(root == null){   //结束条件
            return list;
        }
        list.add(root.val); //根
        preOrderAppend(root.left,list);  //左
        preOrderAppend(root.right,list); //右
        return list;
    }

    /**
     * 后序遍历二叉树（左右根 ）
     * @param root 二叉树头节点
     * @return 按照后序顺序排列好的数组
     */
    public Integer[] postOrderTraverse(TreeNode root) {

        //频繁插入元素的场景，LinkedList性能比ArrayList更高
        LinkedList<Integer> list = new LinkedList<>();
        //将LinkedList转换成普通的数组
        LinkedList<Integer> resultList = postOrderAppend(root, list);
        return resultList.toArray(new Integer[resultList.size()]);
    }

    private LinkedList<Integer> postOrderAppend(TreeNode root, LinkedList<Integer> list){

        if(root == null){   //结束条件
            return list;
        }
        postOrderAppend(root.left,list);  //左
        postOrderAppend(root.right,list); //右
        list.add(root.val); //根
        return list;
    }

    /**
     * 中序遍历二叉树（左根右）
     * 如果将其应用于BST，则得到的是一个有序数组！（应用于普通树得到的是乱序数组）
     * @param root 二叉树头节点
     * @return 按照前序顺序排列好的数组
     */
    public Integer[] inOrderTraverse(TreeNode root) {
        //频繁插入元素的场景，LinkedList性能比ArrayList更高
        LinkedList<Integer> list = new LinkedList<>();
        //将LinkedList转换成普通的数组
        LinkedList<Integer> resultList = inOrderAppend(root, list);
        return resultList.toArray(new Integer[resultList.size()]);
    }

    private LinkedList<Integer> inOrderAppend(TreeNode root, LinkedList<Integer> list) {
        if (root == null) {  //边界检查
            return null;
        }
        if (root.left != null) {
            inOrderAppend(root.left, list);
        }
        list.add(root.val);
        if (root.right != null) {
            inOrderAppend(root.right, list);
        }
        return list;
    }

    /**
     * Leetcode: 1382. 将二叉搜索树变平衡（其实就是让你将一颗二叉搜索树变成一个AVL树）
     * 
     * 注意：你并不需要手撕AVL树，手撕AVL树难度非常大
     * 你要充分利用二叉搜索树的性质：二叉搜索树中序遍历可以得到有序数组
     * 然后通过有序数组构建AVL树，就非常简单了
     * @param root
     * @return
     */
    public TreeNode balanceBST(TreeNode root) {
        //得到一个有序数组
        Integer[] orderArray = inOrderTraverse(root);
        //通过找中点的方法递归建树
        TreeNode BST = initBinarySearchTree(orderArray,0,orderArray.length-1);
        return BST;
    }

    /**
     * LeetCode: 110. 平衡二叉树
     * 判断二叉树是否是高度平衡的(每个结点都必须高度平衡)
     * 思路：遍历子树所有结点，只要有任意一个结点平衡因子大于1，该二叉树就不是高度平衡的
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        //结点是空，或者是叶结点，都是高度平衡的
        if (root == null || root.left==null && root.right==null){
            return true;
        }
        if (balanceFactor(root)>1){
            return false;
        }
        if (!isBalanced(root.left)){
            return false;
        }
        if (!isBalanced(root.right)){
            return false;
        }
        return true;
    }


    //计算某节点的高度. 是LeetCode: 110. 平衡二叉树的子方法
    private int computingHeight(TreeNode root) {
        //空节点 高度是0
        if (root == null){
            return 0;
        }
        //叶结点 高度是1
        if (root.left == null && root.right == null){
            return 1;
        }
        return Math.max(computingHeight(root.left), computingHeight(root.right))+1;
    }
    //计算某结点平衡因子(某结点的左子树与右子树的高度(深度)差的绝对值即为该结点的平衡因子)
    //是LeetCode: 110. 平衡二叉树的子方法
    private int balanceFactor(TreeNode root){
        return Math.abs(computingHeight(root.left) - computingHeight(root.right));
    }




    public static void main(String[] args) {
        BinaryTreeAPI binaryTreeAPI = new BinaryTreeAPI();
        Integer[] testArr2 = {3,9,20,null,null,15,7};
        TreeNode treeNode = binaryTreeAPI.initBinaryTree(testArr2);
        System.out.println(binaryTreeAPI.isBalanced(treeNode));

    }
}

